package codetop.greedy;

public class Code767 {
    public String reorganizeString(String s) {
        int count[]=new int[26];
        int max=0;
        for (int i = 0; i < s.length() ; i++) {
            char c=s.charAt(i);
            count[c-'a']++;
            max=Math.max(max,count[c-'a']);
        }
        if (max>(s.length()+1)/2)return "";
        char []ans=new char[s.length()];
        int index0=0;
        int index1=1;
        for (int i = 0; i <count.length ; i++) {
            char c=(char)('a'+i);
            while (count[i]<=s.length()/2&&count[i]>0&&index1<s.length()){
                  ans[index1]=c;
                  index1+=2;
                  count[i]--;
            }
            while (count[i]>0){
                ans[index0]= c;
                index0+=2;
                count[i]--;
            }
        }
        return new String(ans);
    }
}
